package com.wx.algorithm.sort;

import com.wx.ArrayUtils;

/**
 * @desc: 代码简化版归并排序
 * @author: wx
 * 时间复杂度O(n*long(n))
 * 空间复杂度O(n)
 * 稳定排序-是
 * @time: 2020/3/26 6:19 PM
 */
public class SimpleMergeSort {


    public static void sort(int[] array) {
        if (ArrayUtils.arrayValidation(array)) {
            return;
        }
        merge(array, 0, array.length - 1);
    }

    /**
     * 归并
     */
    private static void merge(int[] array, int startIndex, int endIndex) {

        if (startIndex == endIndex) {
            return;
        }

        //计算中间值
        int middle = startIndex + ((endIndex - startIndex) / 2);
        merge(array, startIndex, middle);
        merge(array, middle + 1, endIndex);
        excretion(array,startIndex,middle + 1 ,endIndex);

    }

    /**
     * 外排
     */
    private static void excretion(int[] array, int startIndex, int middle, int endIndex) {

        int[] temp = new int[endIndex - startIndex + 1];
        int i = 0;
        //记录临时变量
        int tempStartIndex = startIndex;
        int tempMiddle = middle;

        //外排实现
        while (tempStartIndex < middle && tempMiddle <= endIndex) {
            if (array[tempStartIndex] < array[tempMiddle]) {
                temp[i++] = array[tempStartIndex++];
            } else {
                temp[i++] = array[tempMiddle++];
            }

        }

        while (tempStartIndex < middle){
            temp[i++] = array[tempStartIndex++];
        }

        while (tempMiddle <= endIndex){
            temp[i++] = array[tempMiddle++];
        }

        for (int j = 0; j < temp.length; j++) {
              array[startIndex++] = temp[j];
        }

    }

    public static void main(String args[]) {
        ArrayUtils.logarithmicRun(10000,500,20,SimpleMergeSort::sort);
    }



}
